import java.util.*;

public class No048 {
    /**
     * 题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含'a'~'z'的字符。
     * 例如，在字符串"arabcacfr”中，最长的不含重复字符的子字符审是”acfr"，长度为4。
     */
    public int LongestSubstringWithoutDuplication(String str) {
        if (str.length() == 0) return 0;
        int cur = 0;
        int max = 0;
        int[] position = new int[26];
        for (int i = 0; i < 26; i++) {
            position[i] = -1;
        }
        for (int i = 0; i < str.length(); i++) {
            int index = str.charAt(i) - 'a';
            int prevIndex = position[index];
            //没出现过或与上一个字符距离大于cur
            if (prevIndex < 0 || i - prevIndex > cur) {
                cur++;
            }
            // 与上个字符距离小于cur
            else {
                max = Math.max(max, cur);
                cur = i - prevIndex;
            }
            position[index] = i;
        }
        return Math.max(max, cur);
    }

    // [i,j]为滑动窗口
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0, i = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}
